﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Collections;
using ShapeConnectors.MaTrix;//
namespace ShapeConnectors
{
    class Euler:MaTran
    {
        public static List<BuocThucHien> StepEuler=new List<BuocThucHien>();
        Stack<int> st = new Stack<int>();
        string chuoi = null;
        List<int> nhaneuler = new List<int>();
        public string XuatEuler()
        {
            int kq = KTCTEuler();
            if (kq == 1)
            {
                chuoi += "Chu trinh euler: \n";
                for (int i = st.Count - 1; i >= 0; i--)
                    chuoi += st.Pop().ToString() + "->";
            }
            else
                chuoi += "Khong co chu trinh euler";
            return chuoi;
        }
        public void ViSit(int i, int lb)
        {
            nhaneuler[i] = lb;
            for (int j = 0; j < spt; j++)
            {
                if (nhaneuler[j] == 0 && (a[i, j] > 0))
                {
                    ViSit(j, lb);
                }
            }
        }
        public int KTLT()
        {
            int lb = 0;
            for (int i = 0; i < spt; i++)
                nhaneuler.Add(0);
            for (int i = 0; i < spt; i++)
            {
                if (nhaneuler[i] == 0)
                {
                    lb++;
                    ViSit(i, lb);
                }
            }
            if (lb == 1)
                     return 1;
            return 0;
        }
        public void TimDuong(int i)
        {
            
            for (int j = 0; j < spt; j++)
            {
                if (a[i, j] != 0)
                {
                    BuocThucHien buoc = new BuocThucHien();
                    buoc.KhoiTao();
                    //gán đỉnh cần tô vào buoc
                    buoc.Dinhcanto = i;
                    buoc.DinhChon = j;
                    buoc.Canhcanto.SetDinh1(i);
                    buoc.Canhcanto.SetDinh2(j);
                    buoc.Canhcanto.SetTS(a[i,j]);
                    buoc.DinhDuongDi = -1 ;
                    StepEuler.Add(buoc);
                    a[i, j] = a[j, i] = 0;
                    TimDuong(j);
                }
            }
            BuocThucHien buoc1 = new BuocThucHien();
            buoc1.KhoiTao();
            //gán đỉnh cần tô vào buoc
            buoc1.Dinhcanto = i;
            buoc1.DinhChon = -1;
            buoc1.Canhcanto.SetDinh1(i);
            buoc1.Canhcanto.SetDinh2(-1);
            buoc1.Canhcanto.SetTS(-1);
            buoc1.DinhDuongDi = i;
            StepEuler.Add(buoc1);
            st.Push(i);

        }
        public int KTCTEuler()
        {
            int x = 0;
            int co = 0;
            for (int i = 0; i < spt; i++)
            {
                for (int j = 0; j < spt; j++)
                {
                    if (a[i, j] == 1)
                    {
                        x = i;
                        co = 1;
                        break;
                    }
                }
                if (co == 1)
                    break;
            }
            Euler e = this;
            st = new Stack<int>();
            e.TimDuong(x);
            for (int i = 0; i < spt; i++)
            {
                for (int j = 0; j < spt; j++)
                {
                    if (a[i, j] != 0)
                        return 0;
                }
            }
            Stack<int> t = new Stack<int>(st);
            int dau = t.Pop();
            int n = t.Count;
            for (int i = 0; i <= n - 2; i++)
                t.Pop();
            int cuoi = t.Pop();
            if (dau != cuoi)
                return -1;
            return 1;
        }
    }
}
